package algorithm.tree;

import algorithm.model.TreeNode;

/**
 * leetcode
 * https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/
 * Medium
 *
 * 根节点到叶子节点，加起来算一个数字。
 * 求所有数字加起来的和
 * Created by yzy on 2021-04-01 17:04
 */
public class SumNumbers {

    public static void main(String[] args) {
        TreeNode node = TreeNode.getTreeNode(new Integer[]{1,2,3});
        sumNumbers(node);
    }

    /**
     * 0ms,  100.0%
     * 35.8MB,  86.22%
     * 递归和大数相加的思路,每往后进一位，就把前面数字乘以10和当前 val 相加
     * 注意，初始的val为0
     *
     * @param root
     * @return
     */
    public static int sumNumbers(TreeNode root) {
        return sumNumbersNode(root, 0);
    }


    private static int sumNumbersNode(TreeNode node, int preVal){
        if(node == null) return 0;
        int currVal = preVal*10 +node.val;
        if(node.left==null && node.right==null) return currVal;
        return sumNumbersNode(node.left, currVal) + sumNumbersNode(node.right, currVal);
    }
}
